package com.demo.java.OD501_550.OD528;

import java.util.Scanner;
import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【周末爬山(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146495073
 */
public class OdMain {

    // 定义一个全局变量，用来记录遍历的次数
    public static int count = 0;

    public static void main(String[] args) {
        // 创建Scanner对象用于接收输入
        Scanner in = new Scanner(System.in);

        // 输入第一行数据，表示山的长和宽，以及最大能接受的高度差k
        String input_str1 = in.nextLine();
        String[] tmp1 = input_str1.split(" ");
        int[] params = new int[tmp1.length];
        for (int j = 0; j < tmp1.length; j++) {
            params[j] = Integer.parseInt(tmp1[j]); // 将输入的字符串转换为整型数组
        }
        int m = params[0]; // 山的行数
        int n = params[1]; // 山的列数
        int k = params[2]; // 最大能接受的高度差

        // 创建一个m * n的二维数组，表示山的高度矩阵
        int[][] matrix = new int[m][n];

        // 输入每一行的数据，存储山的高度信息
        for (int i = 0; i < m; i++) {
            String input_str = in.nextLine();
            String[] tmp2 = input_str.split(" ");
            int[] nums = new int[tmp2.length];
            for (int j = 0; j < tmp2.length; j++) {
                nums[j] = Integer.parseInt(tmp2[j]);
            }
            for (int j = 0; j < n; j++) {
                matrix[i][j] = nums[j]; // 将每行的数据填充到矩阵中
            }
        }

        // 使用哈希表temp_map存储已经访问过的位置的最大高度
        HashMap<Integer, Integer> temp_map = new HashMap<>();
        temp_map.put(matrix[0][0], 0); // 将起始点的高度存入map，起始点的步数为0

        // 使用栈存储需要继续访问的位置
        ArrayList<int[]> stack = new ArrayList<>();

        // 创建一个二维数组visited，标记哪些位置已经被访问过
        int[][] visited = new int[m][n];

        // 从起点(0,0)开始
        stack.add(new int[]{0, 0});
        visited[0][0] = 1; // 标记起点已经访问

        // 遍历栈中的每一个位置
        while (stack.size() > 0) {
            ArrayList<int[]> empty_stack = new ArrayList<>();
            count += 1; // 记录当前步数
            int i = 0;

            // 遍历当前栈中的所有元素
            while (true) {
                if (i >= stack.size()) {
                    break; // 如果栈为空，跳出循环
                } else {
                    int x = stack.get(i)[0]; // 获取当前栈元素的横坐标
                    int y = stack.get(i)[1]; // 获取当前栈元素的纵坐标

                    int last_height = matrix[x][y]; // 获取当前栈位置的高度

                    // 检查上下左右四个方向是否能继续访问
                    if (x + 1 < m) {
                        if (visited[x + 1][y] == 0) { // 下方位置未被访问过
                            if (Math.abs(matrix[x + 1][y] - matrix[x][y]) <= k) { // 高度差不超过k
                                visited[x + 1][y] = 1; // 标记该位置已访问
                                // 如果该位置的高度在temp_map中未出现，或者步数更小，则更新map
                                if (!temp_map.containsKey(matrix[x + 1][y]) || temp_map.get(matrix[x + 1][y]) > count)
                                    temp_map.put(matrix[x + 1][y], count);
                                empty_stack.add(new int[]{x + 1, y}); // 将该位置添加到栈中
                            }
                        }
                    }
                    if (x - 1 >= 0) {
                        if (visited[x - 1][y] == 0) { // 上方位置未被访问过
                            if (Math.abs(matrix[x - 1][y] - matrix[x][y]) <= k) {
                                visited[x - 1][y] = 1;
                                if (!temp_map.containsKey(matrix[x - 1][y]) || temp_map.get(matrix[x - 1][y]) > count)
                                    temp_map.put(matrix[x - 1][y], count);
                                empty_stack.add(new int[]{x - 1, y});
                            }
                        }
                    }
                    if (y - 1 >= 0) {
                        if (visited[x][y - 1] == 0) { // 左方位置未被访问过
                            if (Math.abs(matrix[x][y - 1] - matrix[x][y]) <= k) {
                                visited[x][y - 1] = 1;
                                if (!temp_map.containsKey(matrix[x][y - 1]) || temp_map.get(matrix[x][y - 1]) > count)
                                    temp_map.put(matrix[x][y - 1], count);
                                empty_stack.add(new int[]{x, y - 1});
                            }
                        }
                    }
                    if (y + 1 < n) {
                        if (visited[x][y + 1] == 0) { // 右方位置未被访问过
                            if (Math.abs(matrix[x][y + 1] - matrix[x][y]) <= k) {
                                visited[x][y + 1] = 1;
                                if (!temp_map.containsKey(matrix[x][y + 1]) || temp_map.get(matrix[x][y + 1]) > count)
                                    temp_map.put(matrix[x][y + 1], count);
                                empty_stack.add(new int[]{x, y + 1});
                            }
                        }
                    }
                }
                i += 1; // 移动到下一个栈元素
            }
            stack = empty_stack; // 更新栈，继续遍历新的位置
        }

        // 找到访问到的最大高度
        int max_height = 0;
        for (Integer key : temp_map.keySet()) {
            max_height = Math.max(max_height, key); // 获取最大高度
        }

        // 输出结果，最大高度及其对应的步数
        System.out.println(max_height + " " + temp_map.get(max_height));
        return;
    }
}
